#include <vector>
#include <iostream>

using namespace std;

// Check if the position `col` in `row` is valid.
bool is_valid_position(int row, int col, vector<int> &records) {
  for (int r = 0; r < row; ++r) {
    bool is_same_col = (records[r] == col);
    bool is_on_diagonal = (abs(r - row) == abs(records[r] - col));

    if (is_same_col || is_on_diagonal) {
      return false;
    }
  }

  return true;
}

int non_attacking_queens(int row, int board_size, vector<int> &records) {
  if (row == board_size) {
    return 1;
  }

  int result = 0;
  for (int col = 0; col < board_size; ++col) {
    if (is_valid_position(row, col, records)) {
      // Try the next row
      records[row] = col;
      result += non_attacking_queens(row + 1, board_size, records);
    }
    else {
      // Try the next col.
    }
  }

  return result;
}

// 一个数组，索引表示行，索引位置上的值，表示列
int solution(int n) {
  vector<int> records(n, 0);
  return non_attacking_queens(0, n, records);
}

int main(int argc, char const *argv[])
{
  
  cout << solution(4) << endl;

  return 0;
}
